https://leetcode-cn.com/problems/generate-parentheses/
前言
因为运气好写了个很漂亮的答案，所以想来分享一下。
怕看了题解就懒了，自己想了一天，走了一点弯路。
弯路
最开始我想的是分情况递归，让括号成对匹配，分为三种情况，第一种是左侧右侧添加()，一种是两边加括号。
但是我发现一个特例，括号按对添加无法生成诸如(())(())这种结果。所以这个思路放弃。
解法思路
既然括号无法成对匹配添加，那就只能一个一个添加了，这里一个个添加主要的问题就是怎么保证括号合法。
我这里用计数的方法来实现，左右括号计数变量分别为l，r，我列个表看一下就懂了。
| 结果 | l | r |
|---|---|---|
| 3 | 3 | |
| ( | 2 | 3 |
| (( | 1 | 3 |
| (() | 1 | 2 |
| (()) | 1 | 1 |
| (())( | 0 | 1 |
| (())() | 0 | 0 |
我们能通过上面这个表总结出几个规律。
l <= r永远成立，因为总要先有(才能有)- 当
l == r只能添加( - 当
l < r时(和)都可以添加
我们现在可以根据上面的规律，总结出递归的判断条件。
- 当
l = 0 and r = 1返回)，递归返回点 - 当
l != 0返回( - 当
l < r返回)
根据上面的规律，只需要两个参数就可以写出一个漂亮的递归函数，如下。
22. 括号生成
https://leetcode-cn.com/problems/generate-parentheses/
- 提交时间:2021-12-01 06:25:39
- 执行用时：32 ms, 在所有 Python3 提交中击败了75.89%的用户
- 内存消耗：15.1 MB, 在所有 Python3 提交中击败了84.39%的用户
- 通过测试用例：8 / 8
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def dp(l: int,r: int):
ret = []
if l == 0 and r == 1:
return [')']
if l != 0:
#可以给'('
for item in dp(l-1,r):
ret.append('(' + item)
if l < r:
#可以给')'
for item in dp(l,r-1):
ret.append(')' + item)
return ret
return dp(n,n)